
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1387. -- [Baltic2002]Moving Robots -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1387: [Baltic2002]Moving Robots</h2><span class=green>Time Limit: </span>2 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>7&nbsp;&nbsp;<span class=green>Solved: </span>1<br>[<a href='submitpage.php?id=1387'>Submit</a>][<a href='problemstatus.php?id=1387'>Status</a>][<a href='bbs.php?id=1387'>Discuss</a>]</center><h2>Description</h2><div class=content>在二维网格平面上有许多机器人在移动。每个机器人的状态由它所在的位置和面向的方位确定。每个机器人按照各自固定的指令执行移动。位置由一对整数(x, y)表示。机器人的方向有4个，用角度表示，分别是0，90，180，270。命令有两种，转身和移动。转身命令有一个参数D，是90，180或270，机器人当前的方向改变D个度数，C度将变为(C&nbsp;+&nbsp;D)&nbsp;mod&nbsp;360。移动指令没有参数，机器人将按它的方向前进一个单位。0方向的移动，位置改变（1，0），方向90改变（0，1），方向180改变（-1，0），方向270改变（0，-1）。
一个机器人依次完成它自己的指令序列。序列执行完后机器人将停在最终的位置上。
两个机器人之间的行动不互相影响，同一个位置可以有多个机器人。
在机器人开始移动前，可以去掉一些指令，所以控制中心可以改变机器人的行动路线和最终位置。控制中心希望使所有的机器人最后到达同一个位置以进行检查。同时希望能够在去掉最少的指令情况下完成这个目标。
任务：
共有R(2&nbsp;<=&nbsp;R&nbsp;<=&nbsp;10)个机器人。每个机器人有它的初始位置，初始方向和命令序列。命令序列长度不超过50。计算需要去掉的最少的命令数
</div><h2>Input</h2><div class=content>Input data should be read from the file robots.in. The first line of the file contains 
integer R (2 ≤ R ≤ 10) – the number of robots. Then R sections of lines follow. Each 
section describes one robot. The first line of the section contains four integers, 
separated by single spaces: x, y – initial robot position (x, y), initial robot direction C 
(C = 0, 90, 180, or 270) and  the  length of  robot’s command  sequence n  (1 ≤ n ≤ 50). 
Then the section contains n lines describing the sequence of commands, one 
command per line. The line of the step command contains single character S in the 
first position and the line of the turn command contains character  T in the first 
position that is followed by turn parameter – integer D (D = 90, 180 or 270) and is 
separated by a single space</div><h2>Output</h2><div class=content>需要去掉的最少的命令数
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>2 <br />
2 0 270 5 <br />
S <br />
T 180 <br />
S <br />
S <br />
S <br />
1 -1 0 8 <br />
S <br />
S <br />
T 90 <br />
S <br />
T 270 <br />
S <br />
T 90 <br />
S </span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>2<br />
</span></div><h2>HINT</h2>
			<div class=content><p>There are 2 moving robots. The first robot has initial position (2, 0), direction 270 and a <br />
sequence of 5 commands. The second one has initial position (1, -1), direction 0 and a <br />
sequence of 8 commands. The minimum total number of commands to be removed that <br />
makes robots share final position is 2: for example, remove the 3-rd command of the <br />
first robot and the 5-th command of the second robot. The common final position in <br />
that case is (2, 1). </p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1387'>Submit</a>][<a href='problemstatus.php?id=1387'>Status</a>][<a href='bbs.php?id=1387'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
